#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int magicalString(int n)
    {
        if (n <= 3) return 1;

        int countOne = 1;
        int front = 3, back = 2;
        std::string s = "122";

        while (front < n)
        {
            if (s[back] == '2')
            {
                if (s[front - 1] == '2')
                {
                    countOne += 2;
                    s += "11";
                    front += 2;

                    if (front == n + 1)
                    {
                        countOne--;
                    }
                }
                else
                {
                    s += "22";
                    front += 2;
                }
            }
            else  // s[back] == '1'
            {
                if (s[front - 1] == '2')
                {
                    countOne += 1;
                    s += "1";
                    front += 1;
                }
                else
                {
                    s += "2";
                    front += 1;
                }
            }

            ++back;
        }

        return countOne;
    }
};